例2

例2 Electricity 电力

Electricity 电力

求一个图删除一个点之后，联通块最多有多少。

• 若 $x$ 是割点
  我们把 $x$ 删掉以后，$x$ 所在的连通块会分成若干个连通块。设 $y$ 为 $x$ 在搜索树上的子节点，并满足条件 $dfn[x] \le low[y]$，那么删掉 $x$ 以后，子树 $y$ 包含的节点将构成一个连通块。最后，不满足 $dfn[x] \le low[y]$ 的子树和 $x$ 的父侧子树将构成另一个连通块。

  

  如上图所示，删掉割点 $x$ 以后，图分成了 $3$ 个连通块。值得注意的是，若 $x$ 是根节点，那么，$x$ 的所有子节点 $y$ 都满足 $dfn[x] \le low[y]$，此时，分成的连通块数量即为 $x$ 的子节点数量。

• 若 $x$ 不是割点
  我们把 $x$ 删掉以后，若连通块仅有 $x$ 一个节点，那么删掉 $x$ 会得到 $0$ 个连通块，否则，依然是一个连通块。在实现的时候，该部分结果与割点部分的代码计算结果一致，具体见参考代码。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 10000 + 5, M = 15e3 + 10;
int p, c;
int head[N], nxt[M << 1], ver[M << 1], tot;
int dfn[N], low[N], tim, c_tot, ans, flag, root;
bool cut[N];

void add(int x, int y) {
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

void dfs(int x) {
    dfn[x] = low[x] = ++tim;
    int parts = 0;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            dfs(y);
            low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y]) parts++;
        } else low[x] = min(low[x], dfn[y]);
    }
    if (x != root) parts++;
    ans = max(ans, pargs);
}

void solve() {
    memset(dfn, 0, sizeof dfn);
    memset(low, 0, sizeof low);
    c_tot = 0;
    ans = 0;
    tot = 1;
    memset(head, 0, sizeof head);
    for (int i = 1; i <= c; i++) {
        int p1, p2; cin >> p1 >> p2;
        p1++, p2++;
        add(p1, p2), add(p2, p1);
    }
    for (int i = 1; i <= p; i++) {
        if (dfn[i]) continue;
        root = i;
        dfs(i);
        c_tot++;
    }
    cout << ans + c_tot - 1 << endl;
}

int main() {
    while (cin >> p >> c && p) solve();
}